package cn.edu.xjtu.算法刷题计划.算法入门.rotate;

import java.util.Arrays;

/**
 * 189. 旋转数组
 * 
 * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        int[] nums = { -1, -100, 3, 99 };
        solu.rotate(nums, 2);
        System.out.println(Arrays.toString(nums));
    }

    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = nums.length - 1;
        int index = 0;
        int preVal = nums[0];
        boolean[] visit = new boolean[nums.length];
        while (count >= 0) {
            int next = (index + k) % nums.length;
            if (visit[next]) {
                index = (index + 1) % nums.length;
                preVal = nums[index];
                continue;
            }
            int temp = nums[next];
            nums[next] = preVal;
            preVal = temp;
            visit[next] = true;
            index = next;
            count--;
        }
    }
}
